package com.logbug.sort;

import java.util.Arrays;

/**
 * 快速排序
 */
public class QuickSort {
    public static void main(String[] args) {
        int[] arr = {2, 3, 1, 4, 7, 6, 4, 4, 8, 9, 3, 2, 4, 5, 7, 6};
        QuickSort sort = new QuickSort(arr);
        sort.sort();
        System.out.println("result = " + Arrays.toString(arr));
    }

    int[] arr;

    public QuickSort(int[] arr) {
        this.arr = arr;
    }

    public void sort() {
        sort(0, arr.length - 1);
    }

    private void sort(int left, int right) {
        if (left < right) {
            int c = left, index = c + 1;
            for (int i = index; i <= right; i++) {
                if (arr[i] < arr[c]) {
                    swap(index++, i);
                }
            }
            swap(--index, c);
            sort(left, index - 1);
            sort(index + 1, right);
        }
    }

    void swap(int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
